\chapter{Вопрос №15}

Решение задачи о раскладке неразличимых предметов по различимым ящикам с помощью обыкновенных производящих функций.

\section{Линейно упорядоченное множество}

Так как предметы неразличмы, то разбить их на два множества заданного размера можно лишь одним способом, и не важно как мы это будем делать, поэтому мы можем просто разложить предметы в линию, провести границу, и разбить предметы на два множества относительно этой границы. Поэтому работать с неразличимыми предметами можно как с линейно упорядоченным множеством.

\section{Раскладка без ограничений}

Если нет ограничений на количество предметов в ящике, то задача о раскладке сводится к обычному разбиению множества предметов, т. е. считаем, что положить некоторое множество в ящик можно ровно одним способом, а это значит, что мы рассматриваем следующую производящую функцию:
\[
	f\left(x\right) = 1 + x + x^2 + x^3 + ... = \frac{1}{1 - x}
\]
если у нас имеется $k$ ящиков, то произведение $k$ таких функций даст нам опф результата:
\[
	h\left(x\right) = \left(\frac{1}{1-x}\right)^k = \sum_{n=0}^\infty \Binomrep{k}{n} x^n
\]

\section{Раскладка с ограничениями}

Рассмотрим сначала самое простое ограничение, когда в каждом ящике не более 1 шара, тогда используем производящую функцию:
\[
	f\left(x\right) = 1+x
\]
а результат соответственно:
\[
	h\left(x\right) = \left(1+x\right)^k = \sum_{n=0}^k \binom{k}{n} x^n
\]

Другой пример, когда не должно быть пустых ящиков, в этом случае рассматриваем производящие функции:
\[
	f\left(x\right) = x + x^2 +x^3 + ... = x\sum_{i=0}^\infty x^i = \frac{x}{1-x}
\]
а результат получается следующим:
\[
	h\left(x\right) = \frac{x^k}{\left(1-x\right)^k} = x^k\sum_{n=0}^\infty \Binomrep{k}{n}x^n
\]
Аналогичным образом произвольные ограничения реализуются через подбор соответствующих производящих функций.
